/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-09-09
 * Time: 14:32
 */
public class TestCode6 {

     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }


        public static boolean isSubStructure(TreeNode A, TreeNode B) {
            // 1. 处理空树：约定空树不是任意一个树的子结构
            if (A == null || B == null) {
                return false;
            }
            // 2. 递归判断：当前节点匹配 || 左子树匹配 || 右子树匹配
            return doesTreeAHasTreeB(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
        }

        // 辅助函数：判断从当前A节点开始，是否包含B（结构相同且值相同）
        private static boolean doesTreeAHasTreeB(TreeNode A, TreeNode B) {
            // 如果B已经遍历完了，说明匹配成功
            if (B == null) {
                return true;
            }
            // 如果A遍历完了但B还有，或者值不相等，说明匹配失败
            if (A == null || A.val != B.val) {
                return false;
            }
            // 递归判断左子树和右子树是否都匹配
            return doesTreeAHasTreeB(A.left, B.left) && doesTreeAHasTreeB(A.right, B.right);
        }

}
